{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time Takes to Reach Destination Without Drowning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSeconds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #避免淹死并到达目的地的最短时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现给定一个 <code>n * m</code> 的索引从 <strong>0</strong> 开始的二维字符串网格 <code>land</code>，目前你站在为&nbsp;<code>\"S\"</code> 的单元格上，你需要到达为&nbsp;<code>\"D\"</code> 的单元格。在这片区域上还有另外三种类型的单元格：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\".\"</code>：这些单元格是空的。</li>\n",
    "\t<li><code>\"X\"</code>：这些单元格是石头。</li>\n",
    "\t<li><code>\"*\"</code>：这些单元格被淹没了。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每秒钟，你可以移动到与当前单元格共享边的单元格（如果它存在）。此外，每秒钟，与被淹没的单元格共享边的每个 <strong>空单元格</strong> 也会被淹没。</p>\n",
    "\n",
    "<p>在你的旅程中，有两个需要注意的问题：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你不能踩在石头单元格上。</li>\n",
    "\t<li>你不能踩在被淹没的单元格上，因为你会淹死（同时，你也不能踩在在你踩上时会被淹没的单元格上）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回从起始位置到达目标位置所需的 <strong>最小</strong> 时间（以秒为单位），如果不可能达到目标位置，则返回 <code>-1</code>。</p>\n",
    "\n",
    "<p><strong>注意</strong>，目标位置永远不会被淹没。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>land = [[\"D\",\".\",\"*\"],[\".\",\".\",\".\"],[\".\",\"S\",\".\"]]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>下面的图片逐秒模拟了土地的变化。蓝色的单元格被淹没，灰色的单元格是石头。\n",
    " 图片（0）显示了初始状态，图片（3）显示了当我们到达目标时的最终状态。正如你所看到的，我们需要 3 秒才能到达目标位置，答案是 3。\n",
    "可以证明 3 是从 S 到 D 所需的最小时间。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/09/ex1.png\" style=\"padding: 5px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 600px; height: 111px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>land = [[\"D\",\"X\",\"*\"],[\".\",\".\",\".\"],[\".\",\".\",\"S\"]]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>下面的图片逐秒模拟了土地的变化。蓝色的单元格被淹没，灰色的单元格是石头。\n",
    "图片（0）显示了初始状态。正如你所看到的，无论我们选择哪条路径，我们都会在第三秒淹没。并且从 S 到 D 的最小路径需要 4 秒。\n",
    "所以答案是 -1。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/09/ex2-2.png\" style=\"padding: 7px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 600px; height: 107px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>land = [[\"D\",\".\",\".\",\".\",\"*\",\".\"],[\".\",\"X\",\".\",\"X\",\".\",\".\"],[\".\",\".\",\".\",\".\",\"S\",\".\"]]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>可以证明我们可以在 6 秒内到达目标位置。同时也可以证明 6 是从 S 到 D 所需的最小秒数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n, m &lt;= 100</code></li>\n",
    "\t<li><code>land</code>&nbsp;只由&nbsp;<code>\"S\"</code>, <code>\"D\"</code>, <code>\".\"</code>, <code>\"*\"</code> 和&nbsp;<code>\"X\"</code>&nbsp;组成。</li>\n",
    "\t<li><strong>恰好</strong>有一个单元格等于&nbsp;<code>\"S\"</code>。</li>\n",
    "\t<li><strong>恰好</strong>有一个单元格等于 <code>\"D\"</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-takes-to-reach-destination-without-drowning](https://leetcode.cn/problems/minimum-time-takes-to-reach-destination-without-drowning/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-takes-to-reach-destination-without-drowning](https://leetcode.cn/problems/minimum-time-takes-to-reach-destination-without-drowning/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"D\",\".\",\"*\"],[\".\",\".\",\".\"],[\".\",\"S\",\".\"]]', '[[\"D\",\"X\",\"*\"],[\".\",\".\",\".\"],[\".\",\".\",\"S\"]]', '[[\"D\",\".\",\".\",\".\",\"*\",\".\"],[\".\",\"X\",\".\",\"X\",\".\",\".\"],[\".\",\".\",\".\",\".\",\"S\",\".\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ids = [i for i in range(n)]\n",
    "        z = sorted(list(zip(nums,ids)))\n",
    "        i,j,k,a = 0,0,0,999999\n",
    "        while i<n:\n",
    "            k,j = 0,i+1\n",
    "            while j<n and z[i][0]==z[j][0]:\n",
    "                k = max(k,(z[j][1] - z[j-1][1])//2)\n",
    "                j += 1\n",
    "            k = max(k,(z[i][1] + n - z[j-1][1])//2)\n",
    "            a = min(a,k)\n",
    "            i = j\n",
    "        \n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        c=Counter(nums)\n",
    "        if len(c)==1:return 0\n",
    "        n=len(nums)\n",
    "        ans=n//2\n",
    "        d=dict()\n",
    "        for i,x in enumerate(nums):\n",
    "            if c[x]==1:\n",
    "                if x in d:\n",
    "                    p,s,dis=d[x]\n",
    "                    d[x]=(i,s,max(dis,i-p,s+n-i))\n",
    "                    c[x]-=1\n",
    "            else:\n",
    "                if x not in d:\n",
    "                    d[x]=(i,i,0)\n",
    "                    c[x]-=1\n",
    "                else:\n",
    "                    p,s,dis=d[x]\n",
    "                    d[x]=(i,s,max(dis,i-p))\n",
    "                    c[x]-=1\n",
    "        # print(d)\n",
    "        for k,(p,s,dis) in d.items():\n",
    "            ans=min(ans,dis//2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans={}\n",
    "        mp={}\n",
    "        for i in range(n):\n",
    "            if nums[i] in mp:\n",
    "                ans[nums[i]]=max(ans[nums[i]],(i-mp[nums[i]])//2) if nums[i] in ans else (i-mp[nums[i]])//2\n",
    "            mp[nums[i]]=i\n",
    "        st=set()\n",
    "        for i in range(n):\n",
    "            if nums[i] in mp and mp[nums[i]]>i and nums[i] not in st:\n",
    "                # print(mp[nums[i]],i)\n",
    "                ans[nums[i]]=max(ans[nums[i]],(n+i-mp[nums[i]])//2) if nums[i] in ans else (n+i-mp[nums[i]])//2\n",
    "                st.add(nums[i])\n",
    "        # print(ans)\n",
    "        return min(ans[a] for a in ans) if len(ans) else n//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mark = [-1] * n\n",
    "        cnt = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in cnt:\n",
    "                mark[i] = cnt[num]\n",
    "            cnt[num] = i\n",
    "        \n",
    "        for i, point in enumerate(mark):\n",
    "            if point == -1:\n",
    "                mark[i] = cnt[nums[i]]\n",
    "        print(mark)\n",
    "        choose = [False] * n\n",
    "        res = inf\n",
    "        for i, j in enumerate(mark):\n",
    "            if choose[i]:\n",
    "                continue\n",
    "            ans = n // 2 if i == j else 0\n",
    "            i1 = i\n",
    "            j1 = j\n",
    "            while choose[i1] == False:\n",
    "                if i1 < j1:\n",
    "                    mid = ((i1 + n - j1 - 1) + 1) // 2\n",
    "                else:\n",
    "                    mid = ((i1 - j1 - 1) + 1) // 2\n",
    "                ans = max(ans, mid)\n",
    "                choose[i1] = True\n",
    "                i1 = j1\n",
    "                j1 = mark[i1]\n",
    "                \n",
    "            res = min(res, ans)\n",
    "        return res\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        record={}\n",
    "        for i in range(len(nums)):\n",
    "            num=nums[i]\n",
    "            if num not in record.keys():\n",
    "                record[num]=(i,i,0)\n",
    "            else:\n",
    "                a,b,c=record[num]\n",
    "                temp=(i-b)//2\n",
    "                record[num]=(a,i,max(temp,c))\n",
    "        ans=len(nums)//2\n",
    "        for i in record.keys():\n",
    "            pos_first,pos_last,temp=record[i]\n",
    "            if pos_first !=pos_last:\n",
    "                pos_first+=len(nums)\n",
    "                temp=max(temp,(pos_first-pos_last)//2)\n",
    "                ans=min(ans,temp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        lastoccur = defaultdict(int)\n",
    "        countstep = defaultdict(int)\n",
    "        for _ in range(2):\n",
    "            for i, num in enumerate(nums):\n",
    "                if num in lastoccur:\n",
    "\n",
    "                    step = (i + n - lastoccur[num]) % n\n",
    "\n",
    "                    if step == 0:\n",
    "                        step = n\n",
    "                        \n",
    "                    countstep[num] = max(countstep[num], step)\n",
    "                    lastoccur[num] = i\n",
    "                else:\n",
    "                    lastoccur[num] = i\n",
    "                \n",
    "        res = min(val for _, val in countstep.items())\n",
    "            \n",
    "                \n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            if x in d:\n",
    "                a = d[x]\n",
    "                d[x] = (a[0], i, max(a[2], i - a[1]))\n",
    "            else:\n",
    "                d[x] = (i, i, 0)\n",
    "        res = n = len(nums)\n",
    "        for _, a in d.items():\n",
    "            res = min(res, max(a[2], a[0] + n - a[1]))\n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        last = {}\n",
    "        dic = defaultdict(int)\n",
    "        \n",
    "        for idx,num in enumerate(nums):\n",
    "            if num in last:\n",
    "                t = (idx - last[num] - 1 + 1) // 2\n",
    "                dic[num] = max(dic[num], t)\n",
    "            last[num] = idx\n",
    "            \n",
    "        \n",
    "        for idx,num in enumerate(nums):\n",
    "            if last[num] != -1:\n",
    "                t = (idx + n - last[num] - 1 + 1) // 2\n",
    "                dic[num] = max(dic[num], t)\n",
    "                last[num] = -1\n",
    "            \n",
    "        ans = 1_000_000_007\n",
    "        for num,val in dic.items():\n",
    "            ans = min(ans, val)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# min max\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dic = dict()\n",
    "        mx = defaultdict(int)\n",
    "        for i, x in enumerate(nums):\n",
    "            if x in dic:\n",
    "                mx[x] = max(mx[x], i - dic[x])\n",
    "                dic[x] = i\n",
    "            else:\n",
    "                dic[x] = i\n",
    "        for i, x in enumerate(nums):\n",
    "            if dic[x] == -1:\n",
    "                continue\n",
    "            if dic[x] == i:\n",
    "                mx[x] = n\n",
    "            if i < dic[x]:\n",
    "                mx[x] = max(mx[x], i + n - dic[x])\n",
    "                dic[x] = -1\n",
    "        # print(mx)\n",
    "        s = min(x for x in mx.values())\n",
    "        # print(s)\n",
    "        return s // 2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos, steps, n = dict(), dict(), len(nums)\n",
    "        for i in range(n):\n",
    "            p = pos.get(nums[i], (-1, -1))\n",
    "            if p[0] != -1:\n",
    "                dist = (i - p[0]) // 2\n",
    "                steps[nums[i]] = max(steps.get(nums[i], 0), dist)\n",
    "            pos[nums[i]] = (i, i if p[1] == -1 else p[1])\n",
    "        \n",
    "        ans = n\n",
    "        for type, p in pos.items():\n",
    "            ans = min(ans, max(steps.get(type, 0), (p[1] + n - p[0]) // 2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        p = {}\n",
    "        for i in range(n):\n",
    "            if nums[i] not in p:\n",
    "                p[nums[i]] = []\n",
    "            p[nums[i]].append(i)\n",
    "        for v in p.values():\n",
    "            pans = 0\n",
    "            for i in range(len(v)):\n",
    "                k = (v[i] - v[i - 1] + n - 1) % n\n",
    "                pans = max(pans, (k + 1) // 2)\n",
    "            ans = min(ans, pans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pre_pos = {}\n",
    "        first_pos = {}\n",
    "        max_dist = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in first_pos:\n",
    "                first_pos[num] = i\n",
    "            if num in pre_pos:\n",
    "                dist = i - pre_pos[num] - 1\n",
    "                if num in max_dist:\n",
    "                    max_dist[num] = max(max_dist[num], dist)\n",
    "                else:\n",
    "                    max_dist[num] = dist\n",
    "            pre_pos[num] = i\n",
    "        res = len(nums)\n",
    "        for num in nums:\n",
    "            dist = first_pos[num] + (len(nums) - pre_pos[num] - 1)\n",
    "            if num in max_dist:\n",
    "                dist = max(max_dist[num], dist)\n",
    "            res = min(res, (dist + 1) // 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        cnt = dict()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if cnt.get(nums[i]) != None:\n",
    "                cnt[nums[i]].append(i)\n",
    "            else:\n",
    "                cnt[nums[i]] = [i]\n",
    "            # cnt[nums[i]] = cnt.get(nums[i],[]).append(i)\n",
    "        \n",
    "        res = n\n",
    "        for x,y in cnt.items():\n",
    "            ans = 0\n",
    "            for i in range(1,len(y)):\n",
    "                ans = max(ans,y[i] - y[i-1]-1)\n",
    "            #print(x,y)\n",
    "            if len(y) == 1: ans = n - 1\n",
    "            else: ans = max(ans,y[0] + n - y[len(y)-1]-1)\n",
    "            res = min(res,(ans + 1) // 2)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        nums = nums + nums \n",
    "        hm = defaultdict(int)\n",
    "        last = dict()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in last:\n",
    "                last[nums[i]] = i\n",
    "            else:\n",
    "                hm[nums[i]] = max(hm[nums[i]], i - last[nums[i]] - 1)\n",
    "                last[nums[i]] = i\n",
    "\n",
    "        res = 1 << 60\n",
    "        for k in hm:\n",
    "            res = min((hm[k] + 1) // 2, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        nums = nums * 2\n",
    "        d = {}\n",
    "        ans = defaultdict(int)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in d:\n",
    "                d[num] = i\n",
    "            else:\n",
    "                ans[num] = max(ans[num], math.ceil((i - d[num] - 1) / 2))\n",
    "                d[num] = i\n",
    "\n",
    "        return min(ans.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = defaultdict(int)\n",
    "        d2 = defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            if d2[nums[i]]:\n",
    "                d[nums[i]] = max(i + 1 - d2[nums[i]][-1], d[nums[i]])\n",
    "            d2[nums[i]].append(i + 1)\n",
    "        ans = n\n",
    "        for key in d:\n",
    "            if len(d2[key]) > 1:\n",
    "                d[key] = max(d2[key][0] + n - d2[key][-1], d[key])\n",
    "                # print(key, d[key])\n",
    "                ans = min(ans, d[key])\n",
    "        return ans // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        dic=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        ans=1000000\n",
    "        for  i in range(n):\n",
    "            dic[nums[i]].append(i)\n",
    "        for idx in dic.values():\n",
    "            #print(idx)\n",
    "            temp=(n-1-idx[-1]+idx[0])\n",
    "            for  i in range(1,len(idx)):\n",
    "                temp=max(temp,idx[i]-idx[i-1]-1)\n",
    "            ans=min(temp,ans)\n",
    "        return (ans+1)//2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 1 2 1 2 1 3 3 3 3 3 3 1 2 1 2 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        last = {}\n",
    "        dist = defaultdict(int)\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n << 1):\n",
    "            v = nums[i if i < n else i - n]\n",
    "            if v in last:\n",
    "                dist[v] = max(dist[v], i - last[v])\n",
    "            last[v] = i\n",
    "        \n",
    "        return min(dist.values()) >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        cnt = collections.defaultdict(list)\n",
    "        for i,ele in enumerate(nums):\n",
    "            cnt[ele].append(i)\n",
    "        \n",
    "        res = len(nums)\n",
    "        for key,pos in cnt.items():\n",
    "            #print(pos)\n",
    "            n = len(pos)\n",
    "            tmp = (len(nums)-1-pos[-1]+pos[0])//2 + (len(nums)-1-pos[-1]+pos[0])%2\n",
    "            for i in range(1,n,1):\n",
    "                #print((pos[i]-pos[i-1]-1)//2, (pos[i]-pos[i-1]-1)%2)\n",
    "                tmp =max(tmp,  (pos[i]-pos[i-1]-1)//2+(pos[i]-pos[i-1]-1)%2)\n",
    "            print(pos,tmp)\n",
    "            res = min(res,tmp)\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        map1=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        res=n//2\n",
    "        for i in range(n):\n",
    "            map1[nums[i]].append(i)\n",
    "        for k,v in map1.items():\n",
    "            left=v[0]\n",
    "            maxl=0\n",
    "            for i in range(len(v)):\n",
    "                maxl=max(maxl,v[i]-left)\n",
    "                left=v[i]\n",
    "            maxl=max(maxl,n+v[0]-left)\n",
    "            res=min(res,(maxl)//2) #1 0 2 1 3 2 4 2\n",
    "        return res\n",
    "                \n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        \n",
    "        index = defaultdict(list)\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            index[num].append(i)\n",
    "        \n",
    "        \n",
    "        t = float('inf')\n",
    "        for vals in index.values():\n",
    "            gap = 0\n",
    "            for i in range(1, len(vals)):\n",
    "                gap = max(gap, abs(vals[i] - vals[i - 1]))\n",
    "            gap = max(gap, len(nums) - vals[-1] + vals[0])\n",
    "            t= min(gap, t)\n",
    "        t -= 1\n",
    "        \n",
    "        print(t)\n",
    "        if t % 2:\n",
    "            return t // 2 + 1\n",
    "        return t // 2\n",
    "        # return math.ceil(gap / 2)\n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        # can we assume the most common number needs to get spanned?\n",
    "        # no, for each index we find where its next identical number is\n",
    "        # that takes // 2 distance\n",
    "        # for each number we do the same\n",
    "        c = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n not in c:\n",
    "                c[n] = []\n",
    "            c[n].append(i)\n",
    "        if len(c) <= 1:\n",
    "            return 0\n",
    "        final_res = 99999\n",
    "        for l in c.values():            \n",
    "            res = 0\n",
    "            for i in range(1, len(l)):\n",
    "                res = max(res, l[i] - l[i-1] - 1)\n",
    "            res = max(res, (len(nums) - 1 - l[-1] + l[0]))\n",
    "            # print(res)\n",
    "            final_res = min(res, final_res)\n",
    "        # print(c)\n",
    "                \n",
    "        return (final_res+1) // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            pos[num].append(i)\n",
    "        ln = len(nums)\n",
    "        minsecs = ln//2\n",
    "        for v in pos.values():\n",
    "            if len(v)>1:\n",
    "                v.append(v[0]+ln)\n",
    "                minsecs = min(max((j-i)//2 for i, j in pairwise(v)), minsecs)\n",
    "        return minsecs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            d[x].append(i)\n",
    "        \n",
    "        res = inf\n",
    "        for x in d:\n",
    "            arr = d[x]\n",
    "            v = 0\n",
    "            for i in range(len(arr)-1):\n",
    "                v = max(v, (arr[i+1] - arr[i] - 1))\n",
    "            v = max(v, (arr[0] + n - 1 - arr[-1]) )\n",
    "            # print(arr, v)\n",
    "            res = min(res, (v+1)//2)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "import math\n",
    "from typing import Optional, List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for k, v in enumerate(nums):\n",
    "            m1[v].append(k)\n",
    "\n",
    "        def get_ans(ll):\n",
    "            if len(ll) == 1:\n",
    "                return math.ceil((len(nums) - 1) / 2)\n",
    "            ret = 0\n",
    "            for k, v in enumerate(ll):\n",
    "                if k == 0:\n",
    "                    v1 = math.ceil((len(nums) - 1 - ll[-1] + v) / 2)\n",
    "                    ret = max(ret, v1)\n",
    "                else:\n",
    "                    v1 = math.ceil((v - ll[k - 1] - 1) / 2)\n",
    "                    ret = max(ret, v1)\n",
    "            return ret\n",
    "        ans = math.inf\n",
    "        for i in m1:\n",
    "            llx = m1[i]\n",
    "            ans = min(ans, get_ans(llx))\n",
    "        return ans\n",
    "\n",
    "a = Solution()\n",
    "# [7,11,7,5]\n",
    "print(a.minimumSeconds([19,20,7,7,20]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        first,pre,pretime={},{},{}\n",
    "        n = len(nums)\n",
    "        ans = n//2\n",
    "        for i,v in enumerate(nums):\n",
    "            if v not in first:\n",
    "                first[v]=i\n",
    "                pretime[v]=0\n",
    "            else:\n",
    "                pretime[v] = max(pretime[v],(i-pre[v])//2)\n",
    "                ans = min(ans,max(pretime[v],(n-i+first[v])//2))\n",
    "            pre[v]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        dic = {} \n",
    "        for i in range(len(nums)) :\n",
    "            if nums[i] in dic: \n",
    "                dic[nums[i]].append(i)\n",
    "            else :\n",
    "                dic[nums[i]] = [i]\n",
    "        #print(\"dic is :\",dic)\n",
    "        rt = [inf]\n",
    "        for x,l in dic.items() :\n",
    "            mx = l[0] \n",
    "            for i in range(1,len(l)) :\n",
    "                mx = max(mx,l[i]-l[i-1]-1)\n",
    "            mx = max( mx,len(nums)-l[-1]+l[0]-1 )\n",
    "            rt.append(mx)\n",
    "        #print(rt)\n",
    "        mn = min(rt)\n",
    "        return (mn+1)//2\n",
    "                \n",
    "        \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        dis = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            dis.setdefault(num, []).append(i)\n",
    "        n = len(nums)\n",
    "        res = n\n",
    "        for diss in dis.values():\n",
    "            diss.append(diss[0] + n)\n",
    "            mx = max((j-i)//2 for i, j in itertools.pairwise(diss))\n",
    "            res = min(res, mx)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i)\n",
    "        ans = n = len(nums)\n",
    "        \n",
    "        for a in pos.values():\n",
    "            a.append(a[0] + n) # 将第一个下标加入数组\n",
    "            mx = max((j - i) // 2 for i, j in pairwise(a))\n",
    "            ans = min(ans, mx)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 把问题看成是【扩散】元素\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i)\n",
    "\n",
    "        ans = n = len(nums)\n",
    "        for a in pos.values():\n",
    "            a.append(a[0] + n)\n",
    "            mx = max((j - i) // 2 for i, j in pairwise(a))\n",
    "            ans = min(ans, mx)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos, steps, n = defaultdict(lambda: (-1, -1)), defaultdict(int), len(nums)\n",
    "        for i in range(n):\n",
    "            pre, first = pos[nums[i]]\n",
    "            if pre != -1:\n",
    "                steps[nums[i]] = max(steps[nums[i]], (i - pre) // 2)\n",
    "            pos[nums[i]] = (i, i if first == -1 else first)\n",
    "\n",
    "        ans = n\n",
    "        for type, p in pos.items():\n",
    "            ans = min(ans, max(steps[type], (p[1] + n - p[0]) // 2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        tw_nums = nums * 2\n",
    "        group = defaultdict(list)\n",
    "        for i, x in enumerate(tw_nums):\n",
    "            group[x].append(i)\n",
    "        res = inf\n",
    "        for _, v in group.items():\n",
    "            mx = -inf\n",
    "            for i in range(1, len(v)):\n",
    "                mx = max(mx, (v[i] - v[i - 1]) // 2)\n",
    "            mx = max(mx, (v[0] + len(v) - v[-1]) // 2)\n",
    "            res = min(res, mx)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        tw_nums = nums * 2\n",
    "        group = defaultdict(list)\n",
    "        for i, x in enumerate(tw_nums):\n",
    "            group[x].append(i)\n",
    "        res = inf\n",
    "        for _, v in group.items():\n",
    "            mx = -inf\n",
    "            for x, y in pairwise(v):\n",
    "                mx = max(mx, (y - x) // 2)\n",
    "            res = min(res, mx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        nums.extend(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            d[v].append(i)\n",
    "            \n",
    "        ans = len(nums)\n",
    "        for _, v in d.items():\n",
    "            max_dis = 0\n",
    "            for i in range(0, len(v) - 1):\n",
    "                max_dis = max(max_dis, (v[i + 1] - v[i]) // 2)\n",
    "            ans = min(ans, max_dis)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pos = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            pos[num].append(i)\n",
    "        \n",
    "        ans = n\n",
    "        for ls in pos.values():\n",
    "            ls.append(ls[0] + n)\n",
    "            mx = max((y - x) // 2 for x, y in pairwise(ls))\n",
    "            ans = min(ans, mx)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        # 最终所有的number都会变成一样的数字\n",
    "        # 而一个num只能变成相邻的数字，也就是说，确定了目标数字，并且得到距离自己最远的要传染的数字，就确定了秒数\n",
    "        # 最长的传染时间是两个最远的相同数字的距离，j - i // 2\n",
    "        pos = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i)\n",
    "        ans = n = len(nums)\n",
    "        for a in pos.values():\n",
    "            a.append(a[0] + n) # 处理环形数组的情况\n",
    "            mx = max((j - i) // 2 for i, j in pairwise(a))\n",
    "            ans = min(ans, mx)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from itertools import pairwise\n",
    "# from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            pos[num].append(i)\n",
    "        res = n = len(nums)\n",
    "        for pos_list in pos.values():\n",
    "            pos_list.append(pos_list[0] + n)\n",
    "            tmp = max((j - i)//2 for i, j in pairwise(pos_list))\n",
    "            res = min(res, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        nums = nums + nums\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            dic[nums[i]].append(i)\n",
    "        res = float('inf')\n",
    "        for v in dic.keys():\n",
    "            index = dic[v]\n",
    "            second = 0\n",
    "            for i in range(1,len(index)):\n",
    "                second = max(second,(index[i]-index[i-1])//2)\n",
    "            res = min(res,second)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,deque\n",
    "from functools import cache\n",
    "import heapq\n",
    "from heapq import heappop,heappush \n",
    "from sortedcontainers import SortedDict,SortedList\n",
    "from itertools import pairwise\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = nums+nums\n",
    "        dic = defaultdict(list)\n",
    "        for i,a in enumerate(nums):\n",
    "            dic[a].append(i)\n",
    "        mx = n \n",
    "        for _,ls in dic.items():\n",
    "            tp = 0\n",
    "            for a,b in pairwise(ls):\n",
    "                tp = max(tp,(b-a)//2)\n",
    "            mx = min(mx,tp)\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumSeconds(self, nums: List[int]) -> int:\n",
    "#         if len(nums) == 1:\n",
    "#             return 0\n",
    "#         origin_cnt = {}\n",
    "#         for i,num in enumerate(nums):\n",
    "#             origin_cnt[num] = 1 if num not in origin_cnt else (origin_cnt[num] + 1)\n",
    "#             if nums[i - 1] == num:origin_cnt[num] += 1\n",
    "#             if nums[i + 1] == num:origin_cnt[num] += 1\n",
    "#         origin_cnt[nums[-1]] = 1 if nums[-1] not in origin_cnt else (origin_cnt[nums[-1]] + 1)\n",
    "#         select = sorted(origin_cnt.items(), key=lambda x:x[0], reverse= True)[0][0]\n",
    "#         second = 1\n",
    "#         cnt = 0\n",
    "#         not_changed = set()\n",
    "#         for i in range(len(nums) - 1):\n",
    "#             if nums[i - 1] == select or nums[i] == select or nums[i + 1] == select:\n",
    "#                 cnt += 1\n",
    "#                 nums[i] == select\n",
    "#             else:\n",
    "\n",
    "#         while cnt < len(nums):\n",
    "#             second += 1\n",
    "#             for i in \n",
    "# class Solution:\n",
    "#     def minimumSeconds(self, nums: List[int]) -> int:\n",
    "#         length = len(nums)\n",
    "#         if length == 1:\n",
    "#             return 0\n",
    "#         max_dis = {}\n",
    "#         for i in range(length):\n",
    "#             if nums[i] not in max_dis:\n",
    "#                 max_dis[nums[i]] = 0\n",
    "#             for j in range(i + 1, i + 1 + length):\n",
    "#                 if nums[i] == nums[j % length]:\n",
    "#                     max_dis[nums[i]] = max(j - i - 1, max_dis[nums[i]])\n",
    "#                     break\n",
    "#         return (sorted(max_dis.items(), key=lambda x:x[1])[0][1] + 1) // 2\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return 0\n",
    "        num_dic = {}\n",
    "        for i in range(length):\n",
    "            if nums[i] not in num_dic:\n",
    "                num_dic[nums[i]] = [i]\n",
    "            else:\n",
    "                num_dic[nums[i]].append(i)\n",
    "        min_res = length\n",
    "        for idxs in num_dic.values():\n",
    "            max_diff = 0\n",
    "            idxs.append(idxs[0] + length)\n",
    "            for i in range(len(idxs) - 1):\n",
    "                max_diff = max(max_diff, idxs[i + 1] - idxs[i])\n",
    "            min_res = min(max_diff, min_res)\n",
    "        return min_res // 2\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        # def func(k: int) -> int:\n",
    "        #     ans = 0\n",
    "        #     left = 0\n",
    "        #     n = len(nums)\n",
    "        #     while left < n:\n",
    "        #         if nums[left] == k: break\n",
    "        #         left += 1\n",
    "        #     m, right = left, left\n",
    "        #     while right < n:\n",
    "        #         if nums[right] == k:\n",
    "        #             ans = max(ans, (right - left) // 2)\n",
    "        #             left = right\n",
    "        #         right += 1\n",
    "        #     ans = max(ans, (m + n - left) // 2)\n",
    "        #     return ans\n",
    "        # 找到元素个数最多的元素\n",
    "        d = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            if x in d:\n",
    "                d[x].append(i)\n",
    "            else:\n",
    "                d[x] = [i]\n",
    "        ans = inf\n",
    "        n = len(nums)\n",
    "        for key in d.keys():\n",
    "            v = d[key]\n",
    "            v.append(v[0] + n)\n",
    "            t = 0\n",
    "            for j in range(1, len(v)):\n",
    "                t = max(t, (v[j] - v[j - 1]) // 2)\n",
    "            ans = min(ans, t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: [int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=n+1\n",
    "\n",
    "        keys=nums+nums\n",
    "#        print(keys)\n",
    "        dc=defaultdict(int)            #dc[i]表示 两个i之间 间隔的最大值\n",
    "        left=defaultdict(int)          #left[i]表示上一个i出现的位置\n",
    "        ss=set()\n",
    "        for i in range(len(keys)):\n",
    "            if keys[i] in ss:\n",
    "                tmp=i-left[keys[i]]\n",
    "                dc[keys[i]]=max(dc[keys[i]], tmp)\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "            left[keys[i]]=i\n",
    "            ss.add(keys[i])\n",
    "\n",
    "        maxed=len(keys)\n",
    "        for k,v in dc.items():\n",
    "            maxed=min(maxed,v)\n",
    "\n",
    "        return maxed//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        n = len(nums)\n",
    "        for i in range(2 * n):\n",
    "            if nums[i % n] in dic:\n",
    "                dic[nums[i % n]].append(i)\n",
    "            else:\n",
    "                dic[nums[i % n]] = [i]                \n",
    "        res = float(\"inf\")\n",
    "        for k, v in dic.items():\n",
    "            max_distance = -float(\"inf\")\n",
    "            for i in range(len(v) - 1):\n",
    "                distance = v[i+1] - v[i]\n",
    "                max_distance = max(max_distance, (distance)//2)\n",
    "                \n",
    "            res = min(res, max_distance)\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "最终一定会变成x，x是nums中的某个数，因此我们可以穷举每一个可能的x，计算最小的变化次数\n",
    "\n",
    "变化次数的计算方法是\n",
    "\n",
    "如果是[2,3,4,2,3,2,2,2]\n",
    "比如这里选2我们要找到两个x间距的最远距离d\n",
    "\n",
    "最终返回最小的d的一半\n",
    "\n",
    "处理循环数组：将两个原始的长度为n数组拼接成一个2n长度的数组\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums.append(nums[i])\n",
    "        d={}\n",
    "        for i,x in enumerate(nums):\n",
    "            try:\n",
    "                d[x].append(i)\n",
    "            except:\n",
    "                d[x] = [i]\n",
    "        ans = inf \n",
    "        for key in d:\n",
    "            cnt = 0\n",
    "            for i in range(len(d[key])-1):\n",
    "                cnt = max(cnt,(d[key][i+1]-d[key][i])//2)\n",
    "            ans = min(ans,cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        hashTable = {}\n",
    "        # 记录元素下标\n",
    "        for i,x in enumerate(nums):\n",
    "            if x not in hashTable:\n",
    "                hashTable[x] = [i]\n",
    "            else:\n",
    "                hashTable[x].append(i)\n",
    "        ans = n = len(nums)\n",
    "        for i in hashTable.values():\n",
    "            time = 0\n",
    "            i.append(i[0] + n) # 这样就相当于是环形数组\n",
    "            for j in range(len(i) - 1):\n",
    "                time = max(time ,(i[j + 1] - i[j]) // 2)\n",
    "            ans = min(ans, time)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        wdp, hdp, m, n, srt, POS = [], [], len(land), len(land[0]), 0, ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        for i in range(m):\n",
    "            for j, v in enumerate(land[i]):\n",
    "                if v == \"X\": land[i][j] = \"*\"\n",
    "                elif v == \"*\": wdp.append([i,j])\n",
    "                elif v == \"S\":\n",
    "                    land[i][j] = \"-\"\n",
    "                    hdp.append([i,j])\n",
    "        while hdp:\n",
    "            nwdp, nhdp, wdp, hdp, srt = wdp, hdp, [], [], srt + 1\n",
    "            for x, y in nwdp:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and land[nx][ny] in \".-\":\n",
    "                        land[nx][ny] = \"*\"\n",
    "                        wdp.append([nx,ny])\n",
    "            for x, y in nhdp:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and land[nx][ny] in \".D\":\n",
    "                        if land[nx][ny] == \"D\": return srt\n",
    "                        land[nx][ny] = \"-\"\n",
    "                        hdp.append([nx,ny])\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        wdp, hdp, m, n, srt, POS = [], [], len(land), len(land[0]), 0, ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        for i in range(m):\n",
    "            for j, v in enumerate(land[i]):\n",
    "                if v == \"X\": land[i][j] = \"*\"\n",
    "                elif v == \"*\": wdp.append([i,j])\n",
    "                elif v == \"S\":\n",
    "                    land[i][j] = \"-\"\n",
    "                    hdp.append([i,j])\n",
    "        while hdp:\n",
    "            nwdp, nhdp, wdp, hdp, srt = wdp, hdp, [], [], srt + 1\n",
    "            for x, y in nwdp:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and land[nx][ny] in \".-\":\n",
    "                        land[nx][ny] = \"*\"\n",
    "                        wdp.append([nx,ny])\n",
    "            for x, y in nhdp:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and land[nx][ny] in \".D\":\n",
    "                        if land[nx][ny] == \"D\": return srt\n",
    "                        land[nx][ny] = \"-\"\n",
    "                        hdp.append([nx,ny])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        n, m = len(land), len(land[0])\n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        \n",
    "        # Initialize BFS queues\n",
    "        you = deque()\n",
    "        water = deque()\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == 'S':\n",
    "                    you.append((i, j, 0))\n",
    "                elif land[i][j] == '*':\n",
    "                    water.append((i, j))\n",
    "        \n",
    "        while you or water:\n",
    "            # Update water flooding\n",
    "            for _ in range(len(water)):\n",
    "                i, j = water.popleft()\n",
    "                \n",
    "                for dx, dy in directions:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if 0 <= x < n and 0 <= y < m and land[x][y] == '.':\n",
    "                        land[x][y] = '*'\n",
    "                        water.append((x, y))\n",
    "            \n",
    "            # Update your position\n",
    "            for _ in range(len(you)):\n",
    "                i, j, time = you.popleft()\n",
    "                \n",
    "                for dx, dy in directions:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if 0 <= x < n and 0 <= y < m:\n",
    "                        if land[x][y] == 'D':\n",
    "                            return time + 1\n",
    "                        elif land[x][y] == '.':\n",
    "                            land[x][y] = 'S'\n",
    "                            you.append((x, y, time + 1))\n",
    "        \n",
    "        return -1\n",
    "\n",
    "# Example usage:\n",
    "land = [\n",
    "    ['S', '.', '.', 'D'],\n",
    "    ['.', 'X', '.', '.'],\n",
    "    ['.', 'X', '.', '.'],\n",
    "    ['*', '.', '.', '.'],\n",
    "]\n",
    "sol = Solution()\n",
    "print(sol.minimumSeconds(land))  # Should return minimum time or -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        n, m = len(land), len(land[0])\n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        \n",
    "        # Initialize BFS queues\n",
    "        you = deque()\n",
    "        water = deque()\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == 'S':\n",
    "                    you.append((i, j, 0))\n",
    "                elif land[i][j] == '*':\n",
    "                    water.append((i, j))\n",
    "        \n",
    "        while you or water:\n",
    "            # Update water flooding\n",
    "            for _ in range(len(water)):\n",
    "                i, j = water.popleft()\n",
    "                \n",
    "                for dx, dy in directions:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if 0 <= x < n and 0 <= y < m and land[x][y] == '.':\n",
    "                        land[x][y] = '*'\n",
    "                        water.append((x, y))\n",
    "            \n",
    "            # Update your position\n",
    "            for _ in range(len(you)):\n",
    "                i, j, time = you.popleft()\n",
    "                \n",
    "                for dx, dy in directions:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if 0 <= x < n and 0 <= y < m:\n",
    "                        if land[x][y] == 'D':\n",
    "                            return time + 1\n",
    "                        elif land[x][y] == '.':\n",
    "                            land[x][y] = 'S'\n",
    "                            you.append((x, y, time + 1))\n",
    "        \n",
    "        return -1\n",
    "\n",
    "# Example usage:\n",
    "land = [\n",
    "    ['S', '.', '.', 'D'],\n",
    "    ['.', 'X', '.', '.'],\n",
    "    ['.', 'X', '.', '.'],\n",
    "    ['*', '.', '.', '.'],\n",
    "]\n",
    "sol = Solution()\n",
    "print(sol.minimumSeconds(land))  # Should return minimum time or -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        n, m = len(land), len(land[0])\n",
    "        def bfs(start, check):\n",
    "            dis = [[inf] * m for _ in range(n)]\n",
    "            vis = [[0] * m for _ in range(n)]\n",
    "            q = deque(start)\n",
    "            for x, y in start:\n",
    "                dis[x][y], vis[x][y] = 0, 1\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                d = dis[x][y]\n",
    "                for dx, dy in (-1, 0), (0, 1), (1, 0), (0, -1):\n",
    "                    a, b = x + dx, y + dy\n",
    "                    if 0 <= a < n and 0 <= b < m and not vis[a][b] and check(a, b, d + 1):\n",
    "                        dis[a][b], vis[a][b] = d + 1, 1\n",
    "                        q.append((a, b))\n",
    "            return dis\n",
    "\n",
    "        S = D = None\n",
    "        flood = []\n",
    "        for x, y in product(range(n), range(m)):\n",
    "            match land[x][y]:\n",
    "                case 'D': D = (x, y)\n",
    "                case 'S': S = (x, y)\n",
    "                case '*': flood.append((x, y))\n",
    "        close = bfs(flood, lambda x, y, d: land[x][y] in 'S.')\n",
    "        ans = bfs([S], lambda x, y, d: land[x][y] in 'D.' and close[x][y] > d)[D[0]][D[1]]\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        wdp, hdp, m, n, srt = [], [], len(land), len(land[0]), 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                v = land[i][j]\n",
    "                if v == \"X\":\n",
    "                    land[i][j] = \"*\"\n",
    "                elif v == \"*\":\n",
    "                    wdp.append([i,j])\n",
    "                elif v == \"S\":\n",
    "                    land[i][j] = \"-\"\n",
    "                    hdp.append([i,j])\n",
    "\n",
    "        # 4向BFS基础模板\n",
    "        POS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        while hdp:\n",
    "            nwdp, nhdp = [], []\n",
    "            for x, y in wdp:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and land[nx][ny] in \".-\":\n",
    "                        land[nx][ny] = \"*\"\n",
    "                        nwdp.append([nx,ny])\n",
    "            # print(wdp,nwdp) \n",
    "            for x, y in hdp:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n:\n",
    "                        if land[nx][ny] == \".\":\n",
    "                            land[nx][ny] = \"-\"\n",
    "                            nhdp.append([nx,ny])\n",
    "                        elif land[nx][ny] == \"D\":\n",
    "                            return srt\n",
    "            # print(hdp,nhdp)     \n",
    "            wdp, hdp, srt = nwdp, nhdp, srt + 1\n",
    "            # for lis in land:\n",
    "            #     print(lis)\n",
    "            # print()\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m=len(land)\n",
    "        n=len(land[0])\n",
    "        grid=[[inf]*n for _ in range(m)]\n",
    "        dx,dy,sx,sy=-1,-1,-1,-1\n",
    "        queue=deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]==\"*\":\n",
    "                    grid[i][j]=-1\n",
    "                    queue.append((i,j))\n",
    "                elif land[i][j]==\"S\":\n",
    "                    sx,sy=i,j\n",
    "                    grid[i][j]=0\n",
    "                elif land[i][j]==\"D\":\n",
    "                    dx,dy=i,j\n",
    "                    grid[dx][dy]=1000000\n",
    "                elif land[i][j]==\"X\":\n",
    "                    grid[i][j]=-1\n",
    "        dirs=[[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        floor=0\n",
    "        while queue:\n",
    "            floor+=1\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                x,y=queue.popleft()\n",
    "                for j in range(4):\n",
    "                    tempx=x+dirs[j][0]\n",
    "                    tempy=y+dirs[j][1]\n",
    "                    if 0<=tempx<m and 0<=tempy<n and grid[tempx][tempy]==inf:\n",
    "                        grid[tempx][tempy]=floor\n",
    "                        queue.append((tempx,tempy))\n",
    "        floor=0\n",
    "        ans=-1\n",
    "        queue.append((sx,sy))\n",
    "        while queue:\n",
    "            floor+=1\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                x,y=queue.popleft()\n",
    "                for j in range(4):\n",
    "                    tempx=x+dirs[j][0]\n",
    "                    tempy=y+dirs[j][1]\n",
    "                    if tempx==dx and tempy==dy:\n",
    "                        ans=floor\n",
    "                        return ans\n",
    "                    if 0<=tempx<m and 0<=tempy<n and grid[tempx][tempy]>floor:\n",
    "                        grid[tempx][tempy]=floor\n",
    "                        queue.append((tempx,tempy))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        n, m = len(land), len(land[0])\n",
    "        def bfs(start, check):\n",
    "            dis = [[inf] * m for _ in range(n)]\n",
    "            vis = [[0] * m for _ in range(n)]\n",
    "            q = deque(start)\n",
    "            for x, y in start:\n",
    "                dis[x][y], vis[x][y] = 0, 1\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                d = dis[x][y]\n",
    "                for dx, dy in (-1, 0), (0, 1), (1, 0), (0, -1):\n",
    "                    a, b = x + dx, y + dy\n",
    "                    if 0 <= a < n and 0 <= b < m and not vis[a][b] and check(a, b, d + 1):\n",
    "                        dis[a][b], vis[a][b] = d + 1, 1\n",
    "                        q.append((a, b))\n",
    "            return dis\n",
    "        S = D = None\n",
    "        flood = []\n",
    "        for x, y in product(range(n), range(m)):\n",
    "            match land[x][y]:\n",
    "                case 'D': D = (x, y)\n",
    "                case 'S': S = (x, y)\n",
    "                case '*': flood.append((x, y))\n",
    "        close = bfs(flood, lambda x, y, d: land[x][y] in 'S.')\n",
    "        ans = bfs([S], lambda x, y, d: land[x][y] in 'D.' and close[x][y] > d)[D[0]][D[1]]\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m=len(land)\n",
    "        n=len(land[0])\n",
    "        grid=[[inf]*n for _ in range(m)]\n",
    "        dx,dy,sx,sy=-1,-1,-1,-1\n",
    "        queue=deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]==\"*\":\n",
    "                    grid[i][j]=-1\n",
    "                    queue.append((i,j))\n",
    "                elif land[i][j]==\"S\":\n",
    "                    sx,sy=i,j\n",
    "                    grid[i][j]=0\n",
    "                elif land[i][j]==\"D\":\n",
    "                    dx,dy=i,j\n",
    "                    grid[dx][dy]=1000000\n",
    "                elif land[i][j]==\"X\":\n",
    "                    grid[i][j]=-1\n",
    "        dirs=[[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        floor=0\n",
    "        while queue:\n",
    "            floor+=1\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                x,y=queue.popleft()\n",
    "                for j in range(4):\n",
    "                    tempx=x+dirs[j][0]\n",
    "                    tempy=y+dirs[j][1]\n",
    "                    if 0<=tempx<m and 0<=tempy<n and grid[tempx][tempy]==inf:\n",
    "                        grid[tempx][tempy]=floor\n",
    "                        queue.append((tempx,tempy))\n",
    "        floor=0\n",
    "        ans=-1\n",
    "        queue.append((sx,sy))\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        while queue:\n",
    "            floor+=1\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                x,y=queue.popleft()\n",
    "                for j in range(4):\n",
    "                    tempx=x+dirs[j][0]\n",
    "                    tempy=y+dirs[j][1]\n",
    "                    if tempx==dx and tempy==dy:\n",
    "                        ans=floor\n",
    "                        return ans\n",
    "                    if 0<=tempx<m and 0<=tempy<n and not vis[tempx][tempy] and grid[tempx][tempy]>floor:\n",
    "                        vis[tempx][tempy]=True\n",
    "                        queue.append((tempx,tempy))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m=len(land)\n",
    "        n=len(land[0])\n",
    "        grid=[[inf]*n for _ in range(m)]\n",
    "        dx,dy,sx,sy=-1,-1,-1,-1\n",
    "        queue=deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]==\"*\":\n",
    "                    grid[i][j]=-1\n",
    "                    queue.append((i,j))\n",
    "                elif land[i][j]==\"S\":\n",
    "                    sx,sy=i,j\n",
    "                    grid[i][j]=0\n",
    "                elif land[i][j]==\"D\":\n",
    "                    dx,dy=i,j\n",
    "                    grid[dx][dy]=1000000\n",
    "                elif land[i][j]==\"X\":\n",
    "                    grid[i][j]=-1\n",
    "        dirs=[[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        floor=0\n",
    "        while queue:\n",
    "            floor+=1\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                x,y=queue.popleft()\n",
    "                for j in range(4):\n",
    "                    tempx=x+dirs[j][0]\n",
    "                    tempy=y+dirs[j][1]\n",
    "                    if 0<=tempx<m and 0<=tempy<n and grid[tempx][tempy]==inf and land[tempx][tempy]!=\"X\":\n",
    "                        grid[tempx][tempy]=floor\n",
    "                        queue.append((tempx,tempy))\n",
    "                    if 0<=tempx<m and 0<=tempy<n and land[tempx][tempy]==\"X\":\n",
    "                        grid[tempx][tempy]=-1\n",
    "        floor=0\n",
    "        ans=-1\n",
    "        queue.append((sx,sy))\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        while queue:\n",
    "            floor+=1\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                x,y=queue.popleft()\n",
    "                for j in range(4):\n",
    "                    tempx=x+dirs[j][0]\n",
    "                    tempy=y+dirs[j][1]\n",
    "                    if tempx==dx and tempy==dy:\n",
    "                        ans=floor\n",
    "                        return ans\n",
    "                    if 0<=tempx<m and 0<=tempy<n and not vis[tempx][tempy] and grid[tempx][tempy]>floor:\n",
    "                        vis[tempx][tempy]=True\n",
    "                        queue.append((tempx,tempy))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m, n = len(land), len(land[0])\n",
    "        dist = [[-1]*n for _ in range(m)]\n",
    "        d = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == '*':\n",
    "                    dist[i][j] = 0\n",
    "                    q.append((i,j))\n",
    "                if land[i][j] == 'S':\n",
    "                    s = (i, j)\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for di, dj in d:\n",
    "                ii, jj = i + di, j + dj\n",
    "                if 0 <= ii < m and 0 <= jj < n and land[ii][jj] == '.' and dist[ii][jj] == -1:\n",
    "                    dist[ii][jj] = dist[i][j] + 1\n",
    "                    q.append((ii, jj))\n",
    "        q.append(s)\n",
    "        dist2 = [[-1]*n for _ in range(m)]\n",
    "        dist2[s[0]][s[1]] = 0\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            if land[i][j] == 'D':\n",
    "                return dist2[i][j]\n",
    "            for di, dj in d:\n",
    "                ii, jj = i+di, j+dj\n",
    "                if 0<=ii<m and 0<=jj<n and (land[ii][jj] in '.D') and (dist[ii][jj] == -1 or dist[ii][jj] > dist2[i][j] + 1) and dist2[ii][jj] == -1:\n",
    "                    dist2[ii][jj] = dist2[i][j] + 1\n",
    "                    q.append((ii, jj))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m, n = len(land), len(land[0])\n",
    "        flood_time = [[inf] * n for _ in range(m)]\n",
    "        dir_x, dir_y = (-1, 1, 0, 0), (0, 0, -1, 1)\n",
    "        q1, q2 = deque(), deque()\n",
    "\n",
    "        for i, line in enumerate(land):\n",
    "            for j, x in enumerate(line):\n",
    "                if x not in '*S': continue\n",
    "                if x == 'S': q2.append((i, j))\n",
    "                else:\n",
    "                    flood_time[i][j] = 0\n",
    "                    q1.append((i, j))\n",
    "\n",
    "        while q1:\n",
    "            x, y = q1.popleft()\n",
    "            for dx, dy in zip(dir_x, dir_y):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n \\\n",
    "                    and land[nx][ny] == '.' \\\n",
    "                    and flood_time[nx][ny] == inf:\n",
    "                    flood_time[nx][ny] = flood_time[x][y] + 1\n",
    "                    q1.append((nx, ny))\n",
    "        \n",
    "        def bfs():\n",
    "            vis = set(q2)\n",
    "            r = 0\n",
    "            while q2:\n",
    "                for _ in range(len(q2)):\n",
    "                    x, y = q2.popleft()\n",
    "                    if land[x][y] == 'D': return r\n",
    "                    for dx, dy in zip(dir_x, dir_y):\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < m and 0 <= ny < n \\\n",
    "                            and land[nx][ny] in \".D\" and (nx, ny) not in vis \\\n",
    "                            and flood_time[nx][ny] > r + 1:\n",
    "                            q2.append((nx, ny))\n",
    "                            vis.add((nx, ny))\n",
    "                r += 1\n",
    "            return -1\n",
    "\n",
    "        # print(flood_time)\n",
    "        return bfs()\n",
    "\n",
    "# [[3, 2, 4, 3, 2, S, 2, 1],\n",
    "#  [i, 1, D, i, 1, 0, 1, 0],\n",
    "#  [1, 0, 1, 3, 2, 1, i, 1],\n",
    "#  [2, 1, i, 4, i, 2, 0, 2]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m,n=len(land),len(land[0])\n",
    "        big=10**9+7\n",
    "        dp=[[big]*n for _ in range(m)]\n",
    "        s,d=[0,0],[0,0]\n",
    "        q=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]=='*':\n",
    "                    q.append((i,j))\n",
    "                    dp[i][j]=0\n",
    "                elif land[i][j]=='S':\n",
    "                    s=[i,j]\n",
    "                    dp[i][j]=-1\n",
    "                elif land[i][j]=='D':\n",
    "                    dp[i][j]=big+1\n",
    "                    d=[i,j]\n",
    "                elif land[i][j]=='X':\n",
    "                    dp[i][j]=-1\n",
    "        t=0\n",
    "        while q:\n",
    "            q,nq=[],q\n",
    "            for x,y in nq:\n",
    "                for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                    if 0<=nx<m and 0<=ny<n and dp[nx][ny]==big:\n",
    "                        q.append((nx,ny))\n",
    "                        dp[nx][ny]=t+1\n",
    "            t+=1\n",
    "        t=0\n",
    "        q=[s]\n",
    "        ck=set()\n",
    "        while q:\n",
    "            q,nq=[],q\n",
    "            for x,y in nq:\n",
    "                if d[0]==x and d[1]==y:return t\n",
    "                for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                    if 0<=nx<m and 0<=ny<n and dp[nx][ny]>t+1 and (nx,ny) not in ck:\n",
    "                        q.append((nx,ny))\n",
    "                        ck.add((nx,ny))\n",
    "            t+=1\n",
    "        return -1\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        n, m = len(land), len(land[0])\n",
    "        path = set()\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == '*':\n",
    "                    q.append((i,j))\n",
    "                elif land[i][j] == 'S':\n",
    "                    path.add((i,j))\n",
    "                    land[i][j] = '*'\n",
    "        q.append(path.pop())\n",
    "        path.add(q[-1])\n",
    "        dist = 0\n",
    "        dij = [-1,0,1,0,-1]\n",
    "        while q:\n",
    "            dist += 1\n",
    "            nq = []\n",
    "            for i,j in q:\n",
    "                for di, dj in zip(dij[1:],dij[:-1]):\n",
    "                    di += i \n",
    "                    dj += j  \n",
    "                    if 0 <= di < n and 0 <= dj < m and land[di][dj] not in ['*','X']:\n",
    "                        if (i,j) in path:\n",
    "                            if land[di][dj] == 'D':\n",
    "                                return dist \n",
    "                            path.add((di,dj))\n",
    "                        else:\n",
    "                            if land[di][dj] == 'D':\n",
    "                                continue\n",
    "                        land[di][dj] = '*'\n",
    "                        nq.append((di,dj))\n",
    "            q = nq \n",
    "            \n",
    "        return -1  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        que = deque()\n",
    "        n, m = len(land), len(land[0])\n",
    "        test = set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == 'S':\n",
    "                    begin = (i, j)\n",
    "                elif land[i][j] == 'D':\n",
    "                    end = (i, j)\n",
    "                elif land[i][j] == '*':\n",
    "                    que.append((i, j))\n",
    "                    test.add((i, j))\n",
    "        tovis = deque()\n",
    "        tovis.append(begin)\n",
    "        t = 0\n",
    "        while tovis:\n",
    "            t += 1\n",
    "            n = len(que)\n",
    "            while n > 0:\n",
    "                n -= 1\n",
    "                x, y = que.popleft()\n",
    "                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < len(land) and 0 <= ny < len(land[0]) and land[nx][ny] != 'X' and land[nx][ny] != 'D' and (nx, ny) not in test:\n",
    "                        que.append((nx, ny))\n",
    "                        test.add((nx, ny))\n",
    "            n = len(tovis)\n",
    "            while n > 0:\n",
    "                n -= 1\n",
    "                x, y = tovis.popleft()\n",
    "                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < len(land) and 0 <= ny < len(land[0]) and land[nx][ny] != 'X' and (nx, ny) not in test:\n",
    "                        tovis.append((nx, ny))\n",
    "                        test.add((nx, ny))\n",
    "                    if (nx, ny) == end:\n",
    "                        return t\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m, n = len(land), len(land[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        g = [[inf] * n for _ in range(m)]\n",
    "        q = deque()\n",
    "        si = sj = 0\n",
    "        for i, row in enumerate(land):\n",
    "            for j, c in enumerate(row):\n",
    "                match c:\n",
    "                    case \"*\":\n",
    "                        q.append((i, j))\n",
    "                    case \"S\":\n",
    "                        si, sj = i, j\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        t = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                g[i][j] = t\n",
    "                for a, b in pairwise(dirs):\n",
    "                    x, y = i + a, j + b\n",
    "                    if (\n",
    "                        0 <= x < m\n",
    "                        and 0 <= y < n\n",
    "                        and not vis[x][y]\n",
    "                        and land[x][y] in \".S\"\n",
    "                    ):\n",
    "                        vis[x][y] = True\n",
    "                        q.append((x, y))\n",
    "            t += 1\n",
    "        t = 0\n",
    "        q = deque([(si, sj)])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        vis[si][sj] = True\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                if land[i][j] == \"D\":\n",
    "                    return t\n",
    "                for a, b in pairwise(dirs):\n",
    "                    x, y = i + a, j + b\n",
    "                    if (\n",
    "                        0 <= x < m\n",
    "                        and 0 <= y < n\n",
    "                        and g[x][y] > t + 1\n",
    "                        and not vis[x][y]\n",
    "                        and land[x][y] in \".D\"\n",
    "                    ):\n",
    "                        vis[x][y] = True\n",
    "                        q.append((x, y))\n",
    "            t += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        n, m = len(land), len(land[0])\n",
    "        d = [[inf] * m for _ in range(n)]\n",
    "        q = deque()\n",
    "        for r in range(n):\n",
    "            for c in range(m):\n",
    "                if land[r][c] == 'S':\n",
    "                    sr, sc = r, c\n",
    "                elif land[r][c] == 'D':\n",
    "                    tr, tc = r, c\n",
    "                elif land[r][c] == '*':\n",
    "                    d[r][c] = 0\n",
    "                    q.append((r, c))\n",
    "\n",
    "        while q:\n",
    "            r, c = q.popleft()\n",
    "            for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                if 0 <= nr < n and 0 <= nc < m and land[nr][nc] == '.' and d[nr][nc] > d[r][c] + 1:\n",
    "                    d[nr][nc] = d[r][c] + 1\n",
    "                    q.append((nr, nc))\n",
    "\n",
    "        q = deque()\n",
    "        q.append((sr, sc, 0))\n",
    "        vis = set()\n",
    "        vis.add((sr, sc))\n",
    "        while q:\n",
    "            r, c, step = q.popleft()\n",
    "            if r == tr and c == tc:\n",
    "                return step\n",
    "            for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                if 0 <= nr < n and 0 <= nc < m and land[nr][nc] != 'X' and (nr, nc) not in vis and step + 1 < d[nr][nc]:\n",
    "                    q.append((nr, nc, step + 1))\n",
    "                    vis.add((nr, nc))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        row = len(land)\n",
    "        col = len(land[0])\n",
    "        start = end = (0, 0)\n",
    "        flood_list = deque()\n",
    "        flood_time = {}\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if land[i][j] == 'S':\n",
    "                    start = (i, j)\n",
    "                elif land[i][j] == 'D':\n",
    "                    end = (i, j)\n",
    "                elif land[i][j] == '*':\n",
    "                    flood_list.append([i, j, 0])\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        while flood_list:\n",
    "            i, j, cur_time = flood_list.popleft()\n",
    "            for di, dj in directions:\n",
    "                ii, jj = i + di, j + dj\n",
    "                if 0 <= ii < row and 0 <= jj < col and land[ii][jj] == '.' and (ii, jj) not in flood_time:\n",
    "                    flood_time[(ii, jj)] = cur_time + 1\n",
    "                    flood_list.append([ii, jj, cur_time + 1])\n",
    "        visited = {start}\n",
    "        queue = [[0, start[0], start[1]]]\n",
    "        while queue:\n",
    "            cur_time, cur_x, cur_y = heappop(queue)\n",
    "            for dx, dy in directions:\n",
    "                nxt_x, nxt_y = cur_x + dx, cur_y + dy\n",
    "                nxt_time = cur_time + 1\n",
    "                if (nxt_x, nxt_y) == end:\n",
    "                    return nxt_time\n",
    "                if not (0 <= nxt_x < row and 0 <= nxt_y < col):\n",
    "                    continue\n",
    "                if (nxt_x, nxt_y) in visited:\n",
    "                    continue\n",
    "                if land[nxt_x][nxt_y] == '.' and nxt_time < flood_time.get((nxt_x, nxt_y), 10000):\n",
    "                    visited.add((nxt_x, nxt_y))\n",
    "                    heappush(queue, [nxt_time, nxt_x, nxt_y])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, a: List[List[str]]) -> int:\n",
    "        m = len(a)\n",
    "        n = len(a[0])\n",
    "        f = set()\n",
    "        w = []\n",
    "        def la():\n",
    "            return 10**10\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                b = a[i][j]\n",
    "                if b=='X':\n",
    "                    f.add((i, j)) \n",
    "                elif b=='D':\n",
    "                    end = (i, j)\n",
    "                elif b=='S':\n",
    "                    st = (i, j) \n",
    "                elif b=='*':\n",
    "                    w.append((i, j))\n",
    "        f.add(end)\n",
    "        v = defaultdict(la)\n",
    "        s = w \n",
    "        for j in s:\n",
    "            v[j] = 0 \n",
    "        while s:\n",
    "            tmp = []\n",
    "            for i, j in s:\n",
    "                for x, y in [[1,0], [-1,0], [0,1], [0,-1]]:\n",
    "                    x += i \n",
    "                    y += j \n",
    "                    if (0<=x<m) and (0<=y<n):\n",
    "                        if (x, y) not in f:\n",
    "                            if (x, y) not in v:\n",
    "                                tmp.append((x, y)) \n",
    "                                v[(x, y)] = v[(i, j)] + 1 \n",
    "\n",
    "            s = tmp   \n",
    "        v1 = v \n",
    "        f.remove(end) \n",
    "        v = defaultdict(int)\n",
    "        v[st] = 0 \n",
    "        s = [st]\n",
    "        while s:\n",
    "            tmp = []\n",
    "            for i, j in s:\n",
    "                for x, y in [[1,0], [-1,0], [0,1], [0,-1]]:\n",
    "                    x += i \n",
    "                    y += j \n",
    "                    if (0<=x<m) and (0<=y<n):\n",
    "                        if (x, y) not in f:\n",
    "                            if (x, y) not in v:\n",
    "                                if (v[(i, j)] + 1) < v1[(x, y)]:\n",
    "                                    tmp.append((x, y)) \n",
    "                                    v[(x, y)] = v[(i, j)] + 1 \n",
    "\n",
    "                                \n",
    "            s = tmp \n",
    "        if end not in v:\n",
    "            return -1  \n",
    "        return v[end]\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param land:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        sources = []\n",
    "        st1, tar = None, None\n",
    "        for k, v in enumerate(land):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if v2 == '*':\n",
    "                    sources.append((k, k2))\n",
    "                if v2 == 'S':\n",
    "                    st1 = k, k2\n",
    "                if v2 == 'D':\n",
    "                    tar = k, k2\n",
    "        dq1 = deque()\n",
    "        for i in sources:\n",
    "            dq1.append((i, 0))\n",
    "        def getM():\n",
    "            return math.inf\n",
    "        used = defaultdict(getM)\n",
    "        while dq1:\n",
    "            cur, st = dq1.popleft()\n",
    "            if cur not in used:\n",
    "                used[cur] = st\n",
    "            else:\n",
    "                if used[cur] <= st:\n",
    "                    continue\n",
    "            used[cur] = st\n",
    "            v1 = cur[0] + 1, cur[1]\n",
    "            if v1[0] < len(land) and land[v1[0]][v1[1]] not in [\"X\", \"D\"]:\n",
    "                dq1.append((v1, st + 1))\n",
    "            v2 = cur[0] - 1, cur[1]\n",
    "            if v2[0] >= 0 and land[v2[0]][v2[1]] not in [\"X\", \"D\"]:\n",
    "                dq1.append((v2, st + 1))\n",
    "            v3 = cur[0], cur[1] - 1\n",
    "            if v3[1] >= 0 and land[v3[0]][v3[1]] not in [\"X\", \"D\"]:\n",
    "                dq1.append((v3, st + 1))\n",
    "            v4 = cur[0], cur[1] + 1\n",
    "            if v4[1] < len(land[0]) and land[v4[0]][v4[1]] not in [\"X\", \"D\"]:\n",
    "                dq1.append((v4, st + 1))\n",
    "        used[tar] = math.inf\n",
    "\n",
    "        dq2 = deque()\n",
    "        used2 = {}\n",
    "        dq2.append((st1, 0))\n",
    "        while dq2:\n",
    "            cur, time1 = dq2.popleft()\n",
    "            if cur == tar:\n",
    "                return time1\n",
    "\n",
    "            if cur not in used2:\n",
    "                used2[cur] = time1\n",
    "            else:\n",
    "                if used2[cur] <= time1:\n",
    "                    continue\n",
    "            used2[cur] = time1\n",
    "            v1 = cur[0] + 1, cur[1]\n",
    "            if v1[0] < len(land) and used[v1] > time1 + 1 and land[v1[0]][v1[1]] != \"X\":\n",
    "                dq2.append((v1, time1 + 1))\n",
    "            v2 = cur[0] - 1, cur[1]\n",
    "            if v2[0] >= 0 and used[v2] > time1 + 1 and land[v2[0]][v2[1]] != \"X\":\n",
    "                dq2.append((v2, time1 + 1))\n",
    "            v3 = cur[0], cur[1] - 1\n",
    "            if v3[1] >= 0 and used[v3] > time1 + 1 and land[v3[0]][v3[1]] != \"X\":\n",
    "                dq2.append((v3, time1 + 1))\n",
    "            v4 = cur[0], cur[1] + 1\n",
    "            if v4[1] < len(land[0]) and used[v4] > time1 + 1 and land[v4[0]][v4[1]] != \"X\":\n",
    "                dq2.append((v4, time1 + 1))\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.minimumSeconds([[\"D\",\".\"],[\".\",\"S\"]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m,n = len(land),len(land[0])\n",
    "        g = defaultdict(list)\n",
    "        for i,j in product(range(m),range(n)):\n",
    "            g[land[i][j]].append((i,j))\n",
    "        W = {(i,j):0 for i,j in g['*']}\n",
    "        Q = [(0,i,j) for i,j in g['*']]\n",
    "        for w,i,j in Q:\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j-1),(i,j+1)]:\n",
    "                if 0<=x<m and 0<=y<n and land[x][y] in '.S' and (x,y) not in W:\n",
    "                    Q.append((w+1,x,y))\n",
    "                    W[(x,y)] = w+1\n",
    "        S,D = g['S'][0],g['D'][0]\n",
    "        pq,d = [(0,*S)],{}\n",
    "        while pq:\n",
    "            w,i,j = heappop(pq)\n",
    "            if (i,j) in d:\n",
    "                continue\n",
    "            if (i,j)==D:\n",
    "                return w\n",
    "            d[(i,j)] = w\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j-1),(i,j+1)]:\n",
    "                if 0<=x<m and 0<=y<n and land[x][y]!='X' and (x,y) not in d:\n",
    "                    if w+1<W.get((x,y),inf):\n",
    "                        heappush(pq,(w+1,x,y))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, land: List[List[str]]) -> int:\n",
    "        m,n = len(land),len(land[0])\n",
    "        g = defaultdict(list)\n",
    "        for i,j in product(range(m),range(n)):\n",
    "            g[land[i][j]].append((i,j))\n",
    "        d = {(i,j):0 for i,j in g['*']}\n",
    "        Q = [(0,i,j) for i,j in g['*']]\n",
    "        for w,i,j in Q:\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j-1),(i,j+1)]:\n",
    "                if 0<=x<m and 0<=y<n and land[x][y] in '.S' and (x,y) not in d:\n",
    "                    Q.append((w+1,x,y))\n",
    "                    d[(x,y)] = w+1\n",
    "        S,D = g['S'][0],g['D'][0]\n",
    "        Q, vis = [(0,*S)], {S}\n",
    "        for w,i,j in Q:\n",
    "            if (i,j)==D:\n",
    "                return w\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j-1),(i,j+1)]:\n",
    "                if 0<=x<m and 0<=y<n and land[x][y]!='X' and (x,y) not in vis:\n",
    "                    if w+1<d.get((x,y),inf):\n",
    "                        Q.append((w+1,x,y))\n",
    "                        vis.add((x,y))\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
